1. Field of the Invention
The invention relates to the general field of memory circuits and devices for digital systems. Particularly, it relates to error checking and correcting (ECC) within content addressable memories (CAMs).
2. Description of Related Art
A typical memory circuit in an integrated circuit (IC) or digital system holds a fixed number of bits or binary digits, that is entries that can be either zero “0” or one “1”. In most memory circuits, devices or systems, the bits are arranged in a rectangle; that is, the memory contains many words (4 million words for example) of data, each word containing a number of bits (32 bits for example). When a processor or another part of the digital system wants to store data into or retrieve data from a typical memory circuit, it simply specifies the address (between zero and 4 million minus one) of the word desired.
Content addressable memories (CAMs) are rather unlike typical memories and their use in modern digital systems is increasing at a dramatic rate. When writing information into a content addressable memory, the data written is divided into a key and a value. When looking up data from the memory, a desired key is specified. The CAM looks for that particular key and either gives back the value previously stored along with the key, or it generates a “miss” flag indicating that no match was found for the desired key. As an analogy, think of the key as being someone's name, and the associated value as being that person's phone number.
Using computers and other digital systems to perform such lookup operations is hardly new. However, a content addressable memory circuit, device or system implements the lookup process in specially designed hardware. The lookup process in a hardware CAM can be performed at a very high rate, approaching if not equaling the rate possible for reading data from a simple rectangular memory circuit.
Needless to say, designing and building a content addressable memory operable at a high speed is substantially more complex than building a simple memory of equivalent capacity to hold information. In particular, a complex circuit is required to compare many stored keys at the same time to determine which, if any, match the desired key specified by the lookup operation.
Another issue with modern memory circuits is that information or data held in memory circuits within is subject to a number of conditions that occasionally cause errors to arise in the data. Such causes include but are not limited to electronic noise that arises during the read or write processes, cross talk from other bits within the memory and decay within the bit storage circuit—often but not always decay over time of an electric charge.
Various error checking and correcting (ECC) techniques are known in the art. Techniques for error detection, correction or both in digital systems include but are not limited to parity, parallel parity, cyclic redundancy checks (CRC) and Hamming codes.
These techniques are based on redundant information. Redundancy is added to data when it is stored in a memory. Then, when the information is read, the data and redundancy are checked for consistency. As an analogy, if a calendar entry indicates that a meeting starts at 1:30, ends at 2:30 and lasts one and one half hours, then there must be an error in the entry; although we can not tell which of the three data points is incorrect without further information.
Codes that provide single error correction and double error detection (SECDED) code are commonly used in modern digital systems. SECDED codes add enough redundancy that if one bit within a word or other unit of memory erroneously changes from zero “0” to one “1” (or visa versa), then which bit changed can be identified, that bit can be inverted and thus the data can be recovered. Further, SECDED codes add enough redundancy that if two bits erroneously change, then the occurrence of the changes can be detected, but the correct value for the data can not be recovered because it is not possible to determine which bits changed.
Content addressable memories complicate memory design and manufacture. Error checking and correcting schemes also complicate memory design and manufacture. Few if any attempts to combine these technologies have been made, due to the complexity of each technology, even standing alone. Further complicating any attempt to design error checking or correcting into a CAM is the high speeds at which it is desired to operate a CAM.
For example, routing data traffic over the Internet or other networks often requires that the address explicitly present in a packet of network traffic be converted into a corresponding local address or into an intermediate address for the packet's next hop. Because many network protocols rely on small sized packets to keep the overall traffic going smoothly, successful network routers may require millions of CAM lookups per second, thus leaving little if any room for delays introduced by error checking.